package oj;

import java.util.LinkedList;
import java.util.Queue;

public class LC1091 {
    int[] dx=new int[]{1,-1,0,0,1,1,-1,-1};
    int[] dy=new int[]{0,0,1,-1,1,-1,1,-1};
    public int shortestPathBinaryMatrix(int[][] grid) {
        int n=grid.length;
        if(grid[0][0]==1) return -1;
        int count=0;
        Queue<int[]> q=new LinkedList<>();
        q.offer(new int[]{0,0,1});
        grid[0][0]=1;
        while(!q.isEmpty()){
            int[] temp=q.poll();
            if(temp[0]==n-1 && temp[1]==n-1) return temp[2];

            for(int i=0;i<8;i++){
                int x=temp[0]+dx[i];
                int y=temp[1]+dy[i];

                if(x>=0 && y>=0 && x<n && y<n && grid[x][y]==0){
                    q.offer(new int[]{x,y,temp[2]+1});
                    grid[x][y]=1;
                }
            }
        }
        return -1;
    }
}
